/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package routefinder.implementation;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.logging.Logger;
import routefinder.City;
import routefinder.Link;
import routefinder.RouteFinder;
import routefinder.RouteFinderExtended;

/**
 * Implements the Dijkstra algorithm.
 * 
 * @author Lucas
 */
public class RouteFinderExtendedImpl implements RouteFinderExtended {

    /**
     * Infinity value for distances.
     */
    public static final int INFINITE_DISTANCE = Integer.MAX_VALUE;
    /**
     * Some value to initialize the priority queue with.
     */
    private static final int INITIAL_CAPACITY = 8;
    

    /**
     * @see RouteFinderExtended#getAllShortestRouteLengths(routefinder.City) 
     */
    public Map<City, Integer> getAllShortestRouteLengths(City startCity) {
        Dijkstra engine = new Dijkstra();
        engine.execute(startCity, null);
        return engine.getShortestDistances();
    }

    /**
     * @see RouteFinder#getShortestRouteLength(routefinder.City, routefinder.City)
     */
    public int getShortestRouteLength(City startCity, City endCity) {
        Integer d = getAllShortestRouteLengths(startCity).get(endCity);
        return (d == null) ? -1 : d;
    }

    class Dijkstra {

        /**
         * The working set of cities, kept ordered by shortest distance.
         *
         * This comparator orders cities according to their shortest distances,
         * in ascending fashion. If two cities have the same shortest distance,
         * we compare the cities themselves.
         */
        private final PriorityQueue<City> unsettledNodes = new PriorityQueue<City>(INITIAL_CAPACITY, new ShortestDistanceComparator());
        /**
         * The set of cities for which the shortest distance to the source
         * has been found.
         */
        private final Set<City> settledNodes = new HashSet<City>();
        /**
         * The currently known shortest distance for all cities.
         */
        private final Map<City, Integer> shortestDistances = new HashMap<City, Integer>();

        /**
         * Initialize all data structures used by the algorithm.
         *
         * @param start the source node
         */
        private void init(City start) {
            settledNodes.clear();
            unsettledNodes.clear();

            shortestDistances.clear();

            // add source
            setShortestDistance(start, 0);
//        unsettledNodes.add(start);
        }

        /**
         * Run Dijkstra's shortest path algorithm on the map.
         * The results of the algorithm are available through
         * {@link #getPredecessor(City)}
         * and
         * {@link #getShortestDistance(City)}
         * upon completion of this method.
         *
         * @param start the starting city
         * @param destination the destination city.
         */
        public void execute(City start, City destination) {
            Logger.getLogger(Dijkstra.class.getName()).info("Executing Dijkstra on: " + start + " " + destination);
            init(start);

            // the current node
            City u;
            // extract the node with the shortest distance
            while ((u = unsettledNodes.poll()) != null) {
                settledNodes.add(u);
                relaxNeighbors(u);
            }
        }

        /**
         * Compute new shortest distance for neighboring nodes and update if a shorter
         * distance is found.
         *
         * @param u the node
         */
        private void relaxNeighbors(City u) {
            for (Link v : getDestinations(u)) {
                // skip node already settled, unless it's the source node, in this case we still want to calculate the real distance to it (ex: C-A-C).
                if (isSettled(v.getCity()) && (getShortestDistance(v.getCity()) != 0)) {
                    continue;
                }

                int shortDist = getShortestDistance(u) + v.getDistance();

                if ((shortDist < getShortestDistance(v.getCity())) || (getShortestDistance(v.getCity()) == 0)) {
                    /**
                     * the 2nd part of this expression assumes that there aren't cities with 0 distance
                     * ("the starting and ending town will not bethe same town.")
                     */
                    // assign new shortest distance and mark unsettled
                    setShortestDistance(v.getCity(), shortDist);
                }
            }
        }

        /**
         * Test a node.
         *
         * @param v the node to consider
         *
         * @return whether the node is settled, ie. its shortest distance
         * has been found.
         */
        private boolean isSettled(City v) {
            return settledNodes.contains(v);
        }

        /**
         * @return the shortest distance from the source to the given city, or
         * {@link Dijkstra#INFINITE_DISTANCE} if there is no route to the destination.
         */
        protected int getShortestDistance(City city) {
            Integer d = shortestDistances.get(city);
            return (d == null) ? INFINITE_DISTANCE : d;
        }

        /**
         * Set the new shortest distance for the given node,
         * and re-balance the queue according to new shortest distances.
         *
         * This method along with getShortestDistance represents the major
         * bottleneck of the algorithm.
         *
         * @param city the node to set
         * @param distance new shortest distance value
         */
        private void setShortestDistance(City city, int distance) {
            unsettledNodes.remove(city);

            // Update the shortest distance.
            shortestDistances.put(city, distance);

            /*
             * Re-balance the queue according to the new shortest distance found
             * (see the comparator the queue was initialized with).
             */
            unsettledNodes.add(city);
        }

        public Map<City, Integer> getShortestDistances() {
            HashMap<City, Integer> casted = (HashMap<City, Integer>) shortestDistances;
            return (HashMap<City, Integer>) casted.clone();
        }


        /**
         * Get the list of cities that can be reached from the given city.
         */
        public List<Link> getDestinations(City city) {
            List<Link> destinations = new ArrayList<Link>();
            if(city!= null){
                destinations = city.getNeighbours();
            }
            return destinations;
        }

        private class ShortestDistanceComparator implements Comparator<City> {

            public int compare(City left, City right) {
                int result = getShortestDistance(left) - getShortestDistance(right);
                if (result == 0) {
                    result = left.getName().compareTo(right.getName());
                }
                return result;
            }
        }
    }
}
